有鑒於昨天學的泡沫排序法,效率篇低,就有某位聰明的科學家發明了快速排序法,其實也有用到一點二元分類的概念。
快速排序 (Quick Sort) 的想法是說,先找一個基準點,然後派兩個代理人分別從資料的兩邊開始往中間找,如果右邊找到一個值比基準點小,左邊找到一個值比基準點大,就讓他們互換。反覆找並互換,直到兩個人相遇。然後再將相遇的點跟基準點互換。第一輪結束。
原始狀態: 基準點 + 一堆資料......
第一輪後的狀態: 比基準點小的資料 + 基準點 + 比基準點大的資料
接下來再分別從兩邊資料做子循環,但做法跟上面一樣,這就用到了遞迴的概念。
較小資料: (小)基準點 + 小資料 --> 小小資料 + (小)基準點 + 小大資料
較大資料: (大)基準點 + 大資料 --> 大小資料 + (大)基準點 + 大大資料
接下來就重複以上的動作,直到排列完畢。
8 6 1 10 5 3 9 2 7 4
8 6 1 10 5 3 9 2 7 4
8 6 1 10 5 3 9 2 7 4
8 6 1 10 5 3 9 2 7 4
8 6 1 4 5 3 9 2 7 10
8 6 1 4 5 3 9 2 7 10
8 6 1 4 5 3 9 2 7 10
8 6 1 4 5 3 9 2 7 10
8 6 1 4 5 3 7 2 9 10
8 6 1 4 5 3 7 2 9 10
2 6 1 4 5 3 7 8 9 10
( 2 6 1 4 5 3 7 ) + 8 (基準點) + ( 9 10 )
較小資料:2 6 1 4 5 3 7
較大資料:9 10
.
.黑箱作業
.
.
最終結果:
1 2 3 4 5 6 7 8 9 10
程式時間複雜度 O(NlogN)
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]
def quicksort(data, left, right): # 輸入資料,和從兩邊開始的位置
if left >= right : # 如果左邊大於右邊,就跳出function
return
i = left # 左邊的代理人
j = right # 右邊的代理人
key = data[left] # 基準點
while i != j:
while data[j] > key and i < j: # 從右邊開始找,找比基準點小的值
j -= 1
while data[i] <= key and i < j: # 從左邊開始找,找比基準點大的值
i += 1
if i < j: # 當左右代理人沒有相遇時,互換值
data[i], data[j] = data[j], data[i]
# 將基準點歸換至代理人相遇點
data[left] = data[i]
data[i] = key
quicksort(data, left, i-1) # 繼續處理較小部分的子循環
quicksort(data, i+1, right) # 繼續處理較大部分的子循環
quicksort(data, 0, len(data)-1)
print(data)
結果為:
data = [23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]
第一次參加鐵人賽,每天都要出文章其實壓力蠻大的,畢竟手頭上還有幾個項目要做。
就努力堅持完賽吧!
大家加油!!!